package com.hot100;

import java.util.Arrays;

public class Solution437 {

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return pathSum(root.left, targetSum) + pathSum(root.right, targetSum) + getPath(root, targetSum);
    }

    public int getPath(TreeNode root, int sum) {
        if (root == null) return 0;
        return (sum == root.val ? 1 : 0) + getPath(root.left, sum - root.val) + getPath(root.right, sum - root.val);
    }

}
